package com.sunny.l61;

public class Solution {
    public void merge(int A[], int m, int B[], int n) {

        if(0 == n){
            return;
        }

        A[m] = Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            int ind = binarySearch(A, 0, m+i, B[i]);
            int tmpS = m+i;
            if(i == n-1){
                tmpS = m+i-1;
            }
            for (int j = tmpS; j >= ind; j--) {
                A[j + 1] = A[j];
            }
            A[ind] = B[i];

        }

//        for(int i=0;i<A.length;i++){
//            System.out.println(A[i]);
//        }

    }
    public int binarySearch(int[] A, int s, int t, int val){
        while (s < t){
            int mid = (s+t)>>1;
//            System.out.println(s+" "+t+" "+mid+" "+A[mid]);
            if(A[mid] > val){
                t = mid;
            }else{
                s = mid+1;
            }
        }
        return s;
    }

    public static void main(String[] args) {

        Solution solution = new Solution();

        int[] A = {1,2,5,6,8,8,8,9,10,0,0,0};
        int[] B = {1,5,6};

        solution.merge(A,9,B,3);

    }
}